package leetcode_141_160;

import utils.ListNode;

import java.util.ArrayList;
import java.util.List;

public class reorderList_143 {
    /**
     * 单链表 L 表示为：
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     */
    public void reorderList(ListNode head) {
        /**
         * 思路是将所有的节点按顺序提取出来后，双向遍历拼接
         * 4ms
         */
        List<ListNode>nodes=new ArrayList<>();
        ListNode root=head;
        while (root!=null){
            nodes.add(root);
            root=root.next;
        }
        int i=0,len=nodes.size();
        for(;i<nodes.size()/2;i++){
            ListNode backNode=nodes.get(len-1-i);  //后边对应的节点
            //移到之前两个节点的中间
            backNode.next=nodes.get(i+1);
            nodes.get(i).next=backNode;
        }
        nodes.get(i).next=null;
    }


    /**
     * 高解递归思路
     * 递归最深层即为中心节点，然后向外回退，过程中对节点进行连接
     */
    public void reorderList2(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        int len = 0;
        ListNode h = head;
        //求出节点数
        while (h != null) {
            len++;
            h = h.next;
        }

        reorderListHelper(head, len);
    }

    private ListNode reorderListHelper(ListNode head, int len) {
        if (len == 1) {
            ListNode outTail = head.next;
            head.next = null;
            return outTail;
        }
        if (len == 2) {
            ListNode outTail = head.next.next;
            head.next.next = null;
            return outTail;
        }
        //得到对应的尾节点，并且将头结点和尾节点之间的链表通过递归处理
        ListNode tail = reorderListHelper(head.next, len - 2);
        ListNode subHead = head.next;//中间链表的头结点
        head.next = tail;
        ListNode outTail = tail.next;  //上一层 head 对应的 tail
        tail.next = subHead;
        return outTail;
    }
}
